// LeetCode 主站 Problem Nr. 494: 目标和

/*
给你一个整数数组 numbers 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
    例如，numbers = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：
	输入：numbers = [1,1,1,1,1], target = 3
	输出：5
	解释：一共有 5 种方法让最终目标和为 3 。
		-1 + 1 + 1 + 1 + 1 = 3
		+1 - 1 + 1 + 1 + 1 = 3
		+1 + 1 - 1 + 1 + 1 = 3
		+1 + 1 + 1 - 1 + 1 = 3
		+1 + 1 + 1 + 1 - 1 = 3

示例 2：
	输入：numbers = [1], target = 1
	输出：1

提示：
    1 <= numbers.length <= 20
    0 <= numbers[i] <= 1000
    0 <= sum(numbers[i]) <= 1000
    -1000 <= target <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "fmt"

func findTargetSumWays(numbers []int, target int) int {
	return method1(numbers, target)
}

// 基于回溯的解法
func method1(numbers []int, target int) int {
	count := 0
	var backtracking func(index, sum int)
	backtracking = func(index, sum int) {
		if index == len(numbers) {
			if sum == target {
				count++
			}
			return
		}

		backtracking(index+1, sum+numbers[index])
		backtracking(index+1, sum-numbers[index])
	}

	backtracking(0, 0)
	return count
}

// 基于动态规划的解法
func method2(numbers []int, target int) int {
	count := 0

	return count
}

func main() {
	numbers := []int{1,1,1,1,1}
	target := 3
	fmt.Println(findTargetSumWays(numbers, target))
}
